The invention pertains to the domain of the processing of images defined by pixels each presenting a characteristic, such as a brightness, defined by the digital value of a function. More specifically, it pertains to a process for the sequential transformation of images, according to which a mode is defined for the scanning of all or part of the image, and the value of each point is modified as a function of a set of associated pixels taking on their values in one or several images and being located within a sliding linear or surface window related to the pixel to be transformed, identical for all pixels and constituting a structuring element. It can be applied in all areas of image analysis and especially in those of pattern recognition and industrial product display, especially in robotics.
Sequential image transformations have been known for a long time. For example, a description can be found in the article by A. Rosenfeld et. al. "Sequential operations in digital picture processing: J, ACM, Vol 13, No. 4, 1966, pp. 471-494.
To facilitate the understanding of the invention, definitions will be first be given for sequential transformations and the terminology which will be adopted, which is that currently utilized in the area of digital image processing.
A digitized image is comprised of a matrix of pixels having m lines and n columns. Each pixel has a value a.sub.ij belonging to a finite family of values v.sub.1, . . , v.sub.k. In practice, k=2.sup.s is adopted, with s being a whole number, (which signifies that each value is represented by a number of s bits and that 2.sup.s levels of quantification are available).
The neighboring pixels of each given pixel will be defined by a neighborhood graph, examples of which will be given below, and which will naturally be different depending on whether the frame utilized is square or hexagonal and on the degree to which the notion of the neighborhood is extended.
An operation on a digitized image will be constituted by a function transforming the matrix of the image into another matrix. The most general function of this type thus has m.times.n arguments if each pixel constitutes an argument and if the matrix has m lines and n columns. The number of arguments is decreased by effecting "local" or "neighborhood" operations. A neighborhood transformation defines the value of the pixel transformed solely as a function of the value of the original pixel and values of the associated pixels, taken in a constant arrangement around the pixel considered. This constant arrangement constitutes a slide window related to the point to be transformed. The pixels can have their value in one or several images. This value can be the value of the points before the transformation has been implemented: in this case, it pertains to a parallel transformation. The structuring element is not necessarily comprised of the immediate neighbors of the point to be transformed. With the notion of immediate neighbors being thus defined through the use of a neighborhood graph, the different types thereof will now be examined.
As an example, the principal neighborhood graphs encountered in practice will now be given.
Square array:
Two neighborhood graphs are currently utilized. They correspond respectively to a four connexity and an eight connexity.
In the case of the four connexity, each pixel x has four neighbors x.sub.1, x.sub.2, x.sub.3, x.sub.4, distributed as follows: ##EQU1##
The distances d between the pixel considered x and each of the neighboring pixels are all equal.
In the case of an eight connexity, each pixel x has eight neighbors, x.sub.1, . . . , x.sub.8 in the following distribution: ##EQU2##
In this case, the distance between:
the pixel considered x on the one hand, each of pixels x.sub.1, x.sub.2, x.sub.3, x.sub.5, x.sub.7, on the other hand, has a value d1=5, PA1 the pixel dx on the one hand, each of pixels x.sub.2, x.sub.4, x.sub.6, x.sub.8, on the other hand, has a value d2=7.
These distances are in the ratio of 7/5=1.4, close to .sqroot.2.
Hexagonal frame:
In this case, a six or twelve connexity can be adopted.
In the first case, each pixel has six neighbors x.sub.1, . . . , x.sub.6, all equidistant from the pixel considered x: ##EQU3##
In the case of the twelve connexity, each pixel has twelve neighbors x.sub.1, . . . , x.sub.12 distributed as follows: ##EQU4##
In this case, the distances between x and all odd index points are equal and have a value of d1=4; the distances between x and all even index points have a value d2=7. As such, the ratio between these two distances is 1.75, close to .sqroot.3.
In the description of the invention, for the sake of simplicity, examples given will be limited to those corresponding only to specific connexities which are typical. But it will be seen that the invention in all cases can be transposed to various possible patterns and connexities.
Neighborhood transformations are conventionally effected by parallel processing. Transformation is done on all points of the image, independently from each other. Arguments (a.sub.j-1, .sub.j-1, . . . a.sub.i+1, .sub.j+1, . . . ) taken into account in the transformation of pixel a.sub.ij are always the values of the pixels in the neighborhood in the initial image. Each of the new pixel values are stored, i.e., value a*.sub.ij for pixel a.sub.ij, but no transformed pixel is utilized before the transformation has been done for all of the m.multidot.n pixels.
This method of transformation presents an advantage which, up to now, has led technicians to adopt in on a virtually exclusive basis: the subjacent algorithms are conceptually simple and it is easy to design a device to implement them. Moreover, the result of the transformation is independent of the mode of image scanning, which allows the usual image scanning method to be used, as well as conventional address generators. But it was not fully appreciated that each transformation taken on an isolated basis is inefficient and in general a great number of successive passes is necessary before the final result is obtained. To reach higher speeds, the processors in a same device must be multiplied, which makes it complex and highly expensive.
Conversely, sequential transformations described in the aforementioned Rosenfeld et. al. article present the characteristic of providing a result which depends on the mode and direction in which the initial image is scanned. If, for example, the initial digital image is explored using a conventional rester scan which will be called "direct video scanning" i.e., line by line, from left to right and top to bottom, a sequential transformation gives, from the initial pixel a.sub.ij on, the transformed pixel a*.sub.ij : EQU a*.sub.i,j =f[(a*.sub.k).sub.k.epsilon.P(i,j), a.sub.ij,(a.sub.k).sub.k.epsilon.F(i,j) ] (1)
Clearly, each time a pixel is transformed, its new value (rather than its value in the initial image) is used as an argument to transform the subsequent points which contain it in their structuring element.
Formula (1) corresponds to scanning in the direct video direction. In this formula, (a*.sub.k), k.epsilon.P(i,j) is the family of points in the neighborhood of a.sub.ij which have already been encountered during the scanning of the image before pixel a.sub.ij and as such have already acquired their new value.
Conversely, (a.sub.k).sub.k.epsilon.F(i,j) designates the group F.sub.ij, the family of points in the neighborhood of the pixel considered a.sub.ij which have not yet been encountered during the scanning of the image at the time pixel a.sub.ij is being processed.
The algorithm corresponding to the sequential transformation in the inverse video scanning direction, i.e. EQU a.sub.mn, a.sub.m,n-1, . . . , a.sub.m1, a.sub.m-1,n, . . . , a.sub.m-1,1, . . . , a.sub.2n, . . . , a.sub.12, a.sub.11
ensues directly from formula (1).